import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-03
 * Time: 23:45
 */
class LRUCache {
    /**
     * 双向链表
     */
    static class DLinkNode{
        public DLinkNode prev;
        public DLinkNode next;
        public int key;
        public int value;
        //        设置成 带头尾节点的双向链表, 那么需要空的构造函数
        public DLinkNode(){}
        public DLinkNode(int key, int value){
            this.key=key;
            this.value= value;
        }
    }
    public HashMap<Integer, DLinkNode> cache;
    public DLinkNode head;
    public DLinkNode tail;
    public int capacity;  // cache 的容量
    public int usedSize;  // cache 中 已经存储的数据量
    public LRUCache(int capacity){
        this.cache=new HashMap<>();
        // 注意这里的 capacity　和 HashMap 的容量可无关
        this.capacity=capacity;
        this.head=new DLinkNode();
        this.tail=new DLinkNode();
//        这里注意不要忘了把 头尾先连接起来
        head.next=tail;
        tail.prev=head;
    }

    public void put(int key, int value){
        DLinkNode node= cache.get(key);
        if(node==null){
            // 1. key 不存在
            // 1.1 增加节点
            DLinkNode newNode =new DLinkNode(key, value);
            // 1.2 放到 map 中
            cache.put(key, newNode);
            // 1.3 放到 双向链表最后
            addToTail(newNode);
            usedSize++;
            // 1.4 判断是否超出 cache 的容量
            if(usedSize>capacity){
                // 1.5 超出 cache 的容量 则 删除第一个节点
                DLinkNode first=head.next;
                remove(first);
                usedSize--;
                // 1.6 注意不要忘记 清除 cache
                cache.remove(first.key);
            }
        }else{
            // 2. key 已经存在
            // 2.1 更新 value
            node.value=value;
            // 2.2 更新该节点的位置
            changeToTail(node);
        }
    }

    private void remove(DLinkNode node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }

    /**
     * 更新节点的位置, 将节点放到最后的位置
     * @param node
     */
    private void changeToTail(DLinkNode node) {
        // 先将该节点原本的连接断开
        remove(node);
        // 再将该节点放到最后位置
        addToTail(node);
    }

    /**
     * 根据 key 得到　value
     * @param key
     * @return
     */
    public int get(int key){
        DLinkNode node=cache.get(key);
        if(node==null){
            return -1;
        }
        // 将该节点放到最后位置
        changeToTail(node);
        // 返回对应的值
        return node.value;
    }

    /**
     * 删除最近最久未使用的节点
     */
    private void deleteFirst() {
        DLinkNode first=head.next;
        head.next=first.next;
        first.next.prev=head;
    }

    /**
     * 将新的节点添加到末尾
     * @param newNode
     */

    private void addToTail(DLinkNode newNode) {
        newNode.prev=tail.prev;
        tail.prev.next=newNode;
        newNode.next=tail;
        tail.prev=newNode;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
